package org.example.myleet.p710;

import java.util.*;

/**
 * 官方解题思路：将靠左边的黑名单数字映射到右边的白名单数字中，从而达到“富集”白名单数字的目的
 */
public class Solution {

    /**
     * blacklist number -> whitelist number
     */
    private Map<Integer, Integer> map;

    private int available;

    private Random random;

    public Solution(int n, int[] blacklist) {
        int m = blacklist.length;
        Set<Integer> blackSet = new HashSet<>(m);
        for (int black : blacklist) {
            blackSet.add(black);
        }
        Arrays.sort(blacklist);
        map = new HashMap<>(m);
        int right = n;
        //从数列末端开始，将黑名单的数字从小到大映射到数列末端的白名单数字中
        for (int black : blacklist) {
            do {
                --right;
            } while (blackSet.contains(right));
            if (right < 0) {
                //可用的白名单数字已经映射完，则不再进行映射
                break;
            }
            //将黑名单的数字从小到大映射到数列末端的白名单数字中
            map.put(black, right);
        }
        random = new Random(System.currentTimeMillis());
        //设置可以取随机数的剩余数字数量
        available = n - m;
    }

    public int pick() {
        int nextRandNumber = random.nextInt(available);
        if (map.containsKey(nextRandNumber)) {
            return map.get(nextRandNumber);
        }
        return nextRandNumber;
    }
}
